"""
二分搜索是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，
如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，
则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

时间复杂度：O(log n)
空间复杂度：O(n)
"""


# 返回 x 在 arr 中的索引，如果不存在返回 -1
# 递归
# arr 有序数组
# low 数组最小下标
# high 数组最大下标
# x 查找值
def binary_search(arr, low, high, x):
    if high >= low:
        mid = int(low + (high - low) / 2)

        # 元素刚好在中间位置
        if arr[mid] == x:
            return mid
        # 元素小于中间位置的元素，只需要再比较左边的元素
        elif arr[mid] > x:
            return binary_search(arr, low, mid - 1, x)
        # 元素大于中间位置的元素，只需要再比较右边的元素
        else:
            return binary_search(arr, mid + 1, high, x)
    else:
        return -1


# 返回 x 在 arr 中的索引，如果不存在返回 -1
# arr 有序数组
# x 查找值
def binary_search2(arr, x):
    low = 0  # 数组最小下标
    high = len(arr) - 1  # 数组最大下标
    while low <= high:
        mid = (low + high) // 2  # 中间数下标
        if arr[mid] == x:  # 如果中间数下标等于x, 返回
            return mid
        elif arr[mid] > x:  # 如果x在中间数左边, 移动high下标
            high = mid - 1
        else:  # 如果x在中间数右边, 移动low下标
            low = mid + 1
    return -1  # x不存在, 返回-1


if __name__ == '__main__':
    test_arr = [2, 3, 4, 10, 40]
    val = 90
    print(binary_search(test_arr, 0, 4, val))
    print(binary_search2(test_arr, val))

